# 第4节Bellman-Ford的队列优化
n = 5
m = 7
a = [[0, 0, 0, 0],
     [0, 1, 2, 2],
     [0, 1, 5, 10],
     [0, 2, 3, 3],
     [0, 2, 5, 7],
     [0, 3, 4, 4],
     [0, 4, 5, 5],
     [0, 5, 3, 6]]
# 初始化dis数组
dis = [99 for i in range(0, n + 1)]
# 选中的顶点
p = 1
dis[p] = 0
# 初始化book
book = [0 for i in range(0, n + 1)]
# 读入每一条边
u = [0 for i in range(0, m + 1)]
v = [0 for i in range(0, m + 1)]
w = [0 for i in range(0, m + 1)]
f = [-1 for i in range(0, n + 1)]
n = [0 for i in range(0, m + 1)]
for i in range(1, m + 1):
    u[i] = a[i][1]
    v[i] = a[i][2]
    w[i] = a[i][3]
    # 关键
    n[i] = f[u[i]]
    f[u[i]] = i
print(u)
print(v)
print(w)
print(f)
print(n)
# 队列
que = [0 for i in range(0, 101)]
head = 1
tail = 1
# 1号顶点入队
que[tail] = p
tail += 1
book[p] = 1  # 标记1号顶点已经入队
while head < tail:
    k = f[que[head]]  # 当前需要处理的队列的首顶点
    while k != -1:  # 扫描当前顶点所有的边
        if dis[v[k]] > dis[u[k]] + w[k]:
            dis[v[k]] = dis[u[k]] + w[k]
            if book[v[k]] == 0:  # 不在队列中
                que[tail] = v[k]
                tail += 1
                book[v[k]] = 1
        k = n[k]
    # 出队
    book[que[head]] = 0
    head += 1

# 输出结果-1号顶点到各顶点距离最小的距离
print('运算结果:')
print(dis)
